package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

/**
 * @ClassName LongestPalindrome
 * @Description LongestPalindrome
 * @Author wanghaiwei
 * @Date 2023/2/1 9:20
 */
public class LongestPalindrome {
    /**
     * 中心扩散法, o(n^2)
     *
     * @param s
     * @return
     */
    public String longestPalindromeCenterSpread(String s) {
        int maxLength = 0;
        int longestStartIdx = 0;
        int longestEndIdx = 0;
        for (int i = 0; i < s.length(); i++) {
            int leftIdx = i - 1;
            int rightIdx = i + 1;
            int currLength = 1; //初始为1，因为当前i就是长度为1的回文串
            //先向右扩散，找到和当前值重复的最右边界，比如abba，当i=1的时候，先向右找到同为b的最右下标，然后再同时两边扩散
            while (rightIdx < s.length() && s.charAt(rightIdx) == s.charAt(i)) {
                rightIdx++;
                currLength++;
            }
            //现在[leftIdx, rightIdx]区间内都是相同的值，下面在从这个区间两边扩散
            while (leftIdx >= 0 && rightIdx < s.length() && s.charAt(leftIdx) == s.charAt(rightIdx)) {
                leftIdx--;
                rightIdx++;
                currLength = currLength + 2;
            }
            if (currLength > maxLength) {
                longestStartIdx = leftIdx + 1;//加1，是因为两边扩散的最后一次成功之后，多执行了一次leftIdx--
                longestEndIdx = rightIdx - 1;//减1，是因为两边扩散的最后一次成功之后，多执行了一次rightIdx++
                maxLength = currLength;
            }
        }
        return s.substring(longestStartIdx, longestEndIdx + 1);
    }

    /**
     * Manacher算法: O(n)
     *
     * @param s
     * @return
     */
    public String longestPalindromeManacher(String s) {
        return "";
    }

    public static void main(String[] args) {
        LongestPalindrome solution = new LongestPalindrome();
        String result = solution.longestPalindromeCenterSpread("babad");
        Assert.isTrue("bab".equals(result), "babad计算错误，预期：bab，实际：" + result);
        result = solution.longestPalindromeCenterSpread("cbbd");
        Assert.isTrue("bb".equals(result), "cbbd计算错误，预期：bb，实际：" + result);
        result = solution.longestPalindromeCenterSpread("abcddcba");
        Assert.isTrue("abcddcba".equals(result), "abcddcba计算错误，预期：abcddcba，实际：" + result);
        result = solution.longestPalindromeCenterSpread("abbabba");
        Assert.isTrue("abbabba".equals(result), "abbabba计算错误，预期：abbabba，实际：" + result);

        //result = solution.longestPalindromeManacher("babad");
        //Assert.isTrue("bab".equals(result), "babad计算错误，预期：bab，实际：" + result);
        //result = solution.longestPalindromeManacher("cbbd");
        //Assert.isTrue("bb".equals(result), "cbbd计算错误，预期：bb，实际：" + result);
        //result = solution.longestPalindromeManacher("abcddcba");
        //Assert.isTrue("abcddcba".equals(result), "abcddcba计算错误，预期：abcddcba，实际：" + result);
        //result = solution.longestPalindromeManacher("abbabba");
        //Assert.isTrue("abbabba".equals(result), "abbabba计算错误，预期：abbabba，实际：" + result);
    }
}
